package com.atguigu.search;
/*
* 插入查找
* 对于一个有序的数列，我们和二分查找法的区别主要是对于mid值的确定
* 二分法对于mid是：mid=left+(right-left)/2
* 插入查找对于mid是：mid=left+(finVal-arr[left])/(arr[right]-arr[left])*(right-left)
* 相对于二分法查找的优势是：可以减少递归的次数
*
* */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr=new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i]=i;
        }
        int i = insertValueSearch(arr, 0, arr.length - 1, 99);
        int i1 = BinarySerach.binarySearch(arr, 0, arr.length - 1, 99);
        System.out.println(i1);
        System.out.println(i);
    }
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        System.out.println("he");
        if(left>right){
            return -1;
        }
        int mid=left+(findVal-arr[left])/(arr[right]-arr[left])*(right-left);
        if(findVal<arr[mid]){
            return insertValueSearch(arr,left,mid-1,findVal);
        }else if(findVal>arr[mid]){
            return insertValueSearch(arr,mid+1,right,findVal);
        }else {
            return mid;
        }
    }
}
